import java.util.*;

public class TextDemo {
    public static List<String> topKFrequent(String[] words, int k) {
        //1、统计单词出现的次数  key:单词   val: 次数
        Map<String,Integer> map = new HashMap<>();
        for (String word : words) {
            if(map.get(word) == null) {
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        //2、建立大小为k的 小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap =
                new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        //比较频率
                        if(o1.getValue().compareTo(o2.getValue()) == 0) {
                            //做一个转换
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        //return o1.getValue()-o2.getValue();
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });

        //遍历map
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                //此时需要和堆顶元素去比较
                Map.Entry<String,Integer> top = minHeap.peek();
                Integer val = top.getValue();
                // entry是当前的元素
                if(val.compareTo(entry.getValue())<0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else if(val.compareTo(entry.getValue()) == 0) {
                    String key = top.getKey();
                    if(key.compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            list.add(key);
        }
        Collections.reverse(list);
        return list;
    }
    public static List<String> f(String[] word,int k){
        Map<String,Integer> map = new TreeMap<>();
        for(String value : word){
            if(map.get(word)==null){
                map.put(value,1);
            }else{
                map.put(value,map.get(value)+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o2.getKey().compareTo(o1.getKey())==0){
                    return o2.getValue().compareTo(o1.getValue());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for(Map.Entry<String,Integer> e : map.entrySet()){
            if(minHeap.size()<k){
                minHeap.offer(e);
            }else{
                Map.Entry<String,Integer> top = minHeap.poll();
                Integer val = top.getValue();
                if(val.compareTo(top.getValue())<0){
                    minHeap.poll();
                    minHeap.offer(e);
                }else if(val.compareTo(top.getValue())==0){
                    String key = top.getKey();
                    if(key.compareTo(e.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(e);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for(int i = 0;i<k;i++){
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
    public static int pivotIndex(int[] array){
        int[] sum = new int[array.length];
        for(int i = 0;i<array.length;i++){
            sum[i] = array[i];
            if(i!=0){
                sum[i]+=sum[i-1];
            }
        }
        if(sum[0]==sum[array.length-1]) return 0;
        for(int i = 1;i<sum.length;i++){
            if(sum[i-1]==sum[sum.length-1]-sum[i]){
                return i;
            }
        }
        return -1;
    }
    public static void func(String str1,String str2){
        Set<Character> set = new HashSet<>();
        str2 = str2.toUpperCase();
        for(int i = 0;i<str2.length();i++){
            set.add(str2.charAt(i));
        }
        str1 = str1.toUpperCase();
        Set<Character> setBroken = new HashSet<>();
        for(int i = 0;i<str1.length();i++){
            if(!set.contains(str1.charAt(i)) && !setBroken.contains(str1.charAt(i))){
                System.out.println(str1.charAt(i));
                setBroken.add(str1.charAt(i));
            }
        }
    }
    public static void main3(String[] args) {
       Scanner scanner = new Scanner(System.in);
       String str = scanner.nextLine();
       String out = scanner.nextLine();
       func(str,out);

    }

    public static void main(String[] args) {
        String str = "fceacd";
        Set<String> set = new HashSet<>();
        set.add("cds");
        set.add("cads");
        System.out.println(set.remove(0));


    }

    public static void main2(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("abc",12);
        map.put("bcd",13);
        map.put("vdfs",78);
        map.put("noway",0);
        map.put("noway",1);
        map.put("Cd",2);
        map.put("Cd",2);
        System.out.println(map);
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        for(Map.Entry<String,Integer> e : entrySet){
            System.out.println(e.getKey());
        }
    }
    public static void main1(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[] array = new int[]{21,53,21,73,81,11,28,92,511,88};

        for(int value : array){
            binarySearchTree.insert(value);
        }
        binarySearchTree.inorder(binarySearchTree.root);
        binarySearchTree.inorder(binarySearchTree.root);

    }
}
